It is possible to do this in O(n) actually. This problem is essentially the same as https://leetcode.com/problems/maximum-gap/ which has an O(n) bucket sort solution.

Runtime fluctuates a lot but this solution beats 100% time (28ms) using the maximum gap solution as a subroutine.

int maxArea(int h, int w, vector<int>& horizontalCuts, vector<int>& verticalCuts) {
    auto [maxHGap, minHCut, maxHCut] = maxGapAndExtrema(horizontalCuts);
    auto [maxVGap, minVCut, maxVCut] = maxGapAndExtrema(verticalCuts);
    
    int maxH, maxV;
    
    if (maxHGap != -1)
        maxH = max({minHCut, h - maxHCut, maxHGap});
    else
        maxH = max(horizontalCuts.front(), h - horizontalCuts.back());
    
    if (maxVGap != -1)
        maxV = max({minVCut, w - maxVCut, maxVGap});
    else
        maxV = max(verticalCuts.front(), w - verticalCuts.back());

    const int m = 1000000007;

    return (static_cast<long>((maxH%m)) * (maxV%m) %m);
}

tuple<int, int, int> maxGapAndExtrema(vector<int>& nums) {
    // Sentinel
    if (nums.size() <= 1)
        return {-1, -1, -1};
    
    int minVal = INT_MAX, maxVal = INT_MIN;
    
    for (int num : nums) {
        minVal = min(minVal, num);
        maxVal = max(maxVal, num);
    }
    
    assert(minVal != maxVal);
    
    const int size = nums.size()-1;
    const int smallestPossibleGap = static_cast<int>(
        ceil(static_cast<double>(maxVal - minVal) / size)
    );

    int* __restrict__ minBuckets = new int[size];
    fill(minBuckets, minBuckets+size, INT_MAX);
    
    int* __restrict__ maxBuckets = new int[size];
    fill(maxBuckets, maxBuckets+size, INT_MIN);
    
    for (int num : nums) {
        if (num == minVal || num == maxVal)
            continue;
        int idx = (num - minVal) / smallestPossibleGap;

        minBuckets[idx] = min(minBuckets[idx], num);
        maxBuckets[idx] = max(maxBuckets[idx], num);
    }

    int maxGap = INT_MIN;
    int prev = minVal;
    
    for (int i=0; i<nums.size()-1; ++i) {
        if (minBuckets[i] == INT_MAX && maxBuckets[i] == INT_MIN)
            continue;
        maxGap = max(maxGap, minBuckets[i] - prev);
        prev = maxBuckets[i];
    }
    
    delete[] minBuckets;
    delete[] maxBuckets;
    return { max(maxGap, maxVal - prev), minVal, maxVal };
}

Pretty well written article. This is a good lesson in clarifying requirements during an interview (needing to sort the arrays).

A dangerous mistake I made is missed the boundary of those numbers and used int instead of long for the max value.. post here to remind myself

Shouldn't this be a Easy? Maybe I am missing something, but what makes this problem a Medium?

FYI, long is 8 bits size and int is 4 bits size, so if I use int for the maxHeight and maxWidth, it will be an overflow and truncated

The operation on the cuts (vertical or horizontal) is the same: find the biggest cut, so the code can be refactored to reuse/reduce number of lines of code :

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        result = [0,0]
        for idx, items in enumerate([(horizontalCuts,h),(verticalCuts,w)]):
            cuts,max_cut = items
            cuts.append(0)
            cuts.append(max_cut)
            cuts.sort()
            for i in range(len(cuts)-1):
                result[idx] = max(result[idx], cuts[i+1]-cuts[i])
        return result[0]*result[1] %(10**9 + 7)

Further more he code can be simplified by extracting the max_cut computation in a stand alone function.

There are magical lines in the >99.5% solution in Python. May I ask if anyone knows why?

if h == 1000000000:
            return 755332975

Why maxDiff is not calculated with leftMost or upperMost condition? i.e. maxHeight = Math.max(maxHeight, horizontalCuts[i] - 0); and maxWidth = Math.max(maxWidth, verticalCuts[i] - 0);

Cannot understand why this fails the final test case . The maxColumn and MaxRow are correctly returned yet the final modulo calculation does not return the result

    Arrays.sort(horizontalCuts);
    Arrays.sort(verticalCuts);
    int[] modifiedHorizontalCuts = new int[horizontalCuts.length+2];
    int[] modifiedVerticalCuts = new int[verticalCuts.length+2];
    for(int i = 0;i<modifiedHorizontalCuts.length;i++){
        if(i==0) {
            modifiedHorizontalCuts[i] = 0;
            continue;
        }
        if(i==modifiedHorizontalCuts.length-1) {
            modifiedHorizontalCuts[i] = h;
            continue;
        }
        modifiedHorizontalCuts[i] = horizontalCuts[i-1];
    }
    
    for(int i = 0;i<modifiedVerticalCuts.length;i++){
        if(i==0) {
            modifiedVerticalCuts[i] = 0;
            continue;
        }
        if(i==modifiedVerticalCuts.length-1) {
            modifiedVerticalCuts[i] = w;
            continue;
        }
        modifiedVerticalCuts[i] = verticalCuts[i-1];
    }
    
    int maxRow = 0;
    for(int i=1;i<modifiedHorizontalCuts.length;i++){
        maxRow = Math.max(maxRow,modifiedHorizontalCuts[i]-modifiedHorizontalCuts[i-1]);
    }
    
    int maxColumn = 0;
    for(int i=1;i<modifiedVerticalCuts.length;i++){
        maxColumn = Math.max(maxColumn,modifiedVerticalCuts[i]-modifiedVerticalCuts[i-1]);
    }
    // if(h==1000000000)
    //     System.out.println("Max Column "+maxColumn+" Max Row"+maxRow);
    //return (int)  ( ( maxColumn * maxRow ) % (1e9 + 7) );
    return (int) ((maxColumn * maxRow) % (1e9 + 7));`

Why does this fail for the final Testcase? Can anyone please suggest?

class Solution {
    public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
        Arrays.sort(horizontalCuts);
        Arrays.sort(verticalCuts);
        
        int largestHorizontal = getLargestPiece(horizontalCuts, h);
        int largestVertical = getLargestPiece(verticalCuts, w);
        
        return (int) ((largestHorizontal * largestVertical) % 1000000007);
    }
    
    private int getLargestPiece(int[] cuts, int total){
        int prevCut = 0;
        int largestPiece = 0;
        
        for(int cut : cuts){
            int currentPiece = cut - prevCut;
            largestPiece = Math.max(largestPiece, currentPiece);
            prevCut = cut;
        }
        largestPiece = Math.max(largestPiece, total - prevCut);
        
        return largestPiece;
    } 
}